#include<iostream>
#include<string>
#include<>

using namespace std;
class Solution {
//public:
//    string ret = "";
//    string tree2str(TreeNode* root) {
//        if (root == nullptr)
//            return "";
//        ret += to_string(root->val);
//
//        if (root->left || root->right)
//        {
//            ret += "(";
//            tree2str(root->left);
//            ret += ")";
//        }
//        if (root->right)
//        {
//            ret += "(";
//            tree2str(root->right);
//            ret += ")";
//        }
//
//        return ret;
//    }
//};

//class Solution {
//public:
//    bool IsInTree(TreeNode* root, TreeNode* x)
//    {
//        if (root == nullptr)
//            return false;
//        return root == x
//            || IsInTree(root->left, x)
//            || IsInTree(root->right, x);
//    }
//
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (root == nullptr)
//            return nullptr;
//
//        if (root == p || root == q)
//            return root;
//
//        bool pLeft, pRight, qLeft, qRight;
//        pLeft = IsInTree(root->left, p);
//        pRight = !pLeft;
//
//        qLeft = IsInTree(root->left, q);
//        qRight = !qLeft;
//
//        if ((qLeft && pRight) || (qRight && pLeft))
//            return root;
//        else if (qLeft && pLeft)
//            return lowestCommonAncestor(root->left, p, q);
//        else if (qRight && pRight)
//            return lowestCommonAncestor(root->right, p, q);
//        else
//            return nullptr;
//    }
//};


  /*  class Solution {
    public:
        bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& Path)
        {
            if (root == nullptr)
                return false;
            Path.push(root);

            if (root == x)
                return true;

            if (GetPath(root->left, x, Path))
                return true;
            if (GetPath(root->right, x, Path))
                return true;

            Path.pop();
            return false;
        }

        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            stack<TreeNode*> pPath, qPath;
            GetPath(root, p, pPath);
            GetPath(root, q, qPath);

            while (pPath.size() != qPath.size())
            {
                if (pPath.size() > qPath.size())
                    pPath.pop();
                else
                    qPath.pop();
            }

            while (pPath.top() != qPath.top())
            {
                pPath.pop();
                qPath.pop();
            }
            return pPath.top();

        }
    };*/


  /*  class Solution {

    public:
        void InOrderConvert(TreeNode* cur, TreeNode*& prev)
        {
            if (cur == nullptr)
                return;
            InOrderConvert(cur->left, prev);
            cur->left = prev;
            if (prev)
                prev->right = cur;
            prev = cur;

            InOrderConvert(cur->right, prev);
        }

        TreeNode* Convert(TreeNode* pRootOfTree) {
            TreeNode* prev = nullptr;
            InOrderConvert(pRootOfTree, prev);

            TreeNode* head = pRootOfTree;
            while (head && head->left)
            {
                head = head->left;
            }
            return head;
        }
    };*/